class Solution:
    def nthMagicalNumber(self, N: int, A, B):
        """
        :type N: int
        :type A: int
        :type B: int
        :rtype: int
        """
        list_A = []
        list_B = []
        list_AB = []
        value = 0
        if A==B:
            return A*N%1000000007
        A,B = min(A,B),max(A,B)
        AB_num = 0
        num = N//2
        while AB_num<N:
            num += num // 2
            A_num = A*N//2
            B_num = A_num//B
            AB_num = A_num+B_num
        
        print(num)
        return num%1000000007
        
        
        for value in range(1, N + 1):
            list_A.append(A * value)
            list_B.append(B * value)
            value += 2
            if value > N:
                break
        list_AB.extend(list_A)
        list_AB.extend(list_B)
        
        list_AB_set = list(set(list_AB))
        list_AB_set.sort()
        return list_AB_set[N - 1] %1000000007


def main():
    sol = Solution()
    print(sol.nthMagicalNumber(1000000000,3999,40000))


if __name__ == "__main__":
    main()
